//! 哈希索引实现
//! 
//! 实现高性能的哈希索引，支持O(1)平均查找时间

use crate::sql::Value;
use crate::{Error, Result};
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

/// 哈希索引
#[derive(Debug)]
pub struct HashIndex {
    /// 哈希桶
    buckets: Vec<Vec<HashEntry>>,
    /// 桶的数量
    bucket_count: usize,
    /// 总条目数
    size: usize,
    /// 负载因子阈值
    load_factor_threshold: f64,
}

/// 哈希条目
#[derive(Debug, Clone)]
struct HashEntry {
    /// 键
    key: Value,
    /// 值
    value: usize,
}

/// 哈希索引统计信息
#[derive(Debug, Clone)]
pub struct HashStatistics {
    /// 总条目数
    pub total_entries: usize,
    /// 桶数量
    pub bucket_count: usize,
    /// 负载因子
    pub load_factor: f64,
    /// 最大链长度
    pub max_chain_length: usize,
    /// 平均链长度
    pub avg_chain_length: f64,
    /// 空桶数量
    pub empty_buckets: usize,
}

impl HashIndex {
    /// 创建新的哈希索引
    pub fn new(initial_bucket_count: usize) -> Self {
        let bucket_count = initial_bucket_count.max(16); // 最少16个桶
        
        Self {
            buckets: vec![Vec::new(); bucket_count],
            bucket_count,
            size: 0,
            load_factor_threshold: 0.75,
        }
    }
    
    /// 插入键值对
    pub fn insert(&mut self, key: Value, value: usize) -> Result<()> {
        // 检查是否需要扩容
        if self.load_factor() > self.load_factor_threshold {
            self.resize()?;
        }
        
        let hash = self.hash_key(&key);
        let bucket_index = hash % self.bucket_count;
        
        // 检查是否已存在相同的键
        let bucket = &mut self.buckets[bucket_index];
        for entry in bucket.iter_mut() {
            if entry.key == key {
                // 更新现有条目（或添加重复键）
                bucket.push(HashEntry { key, value });
                self.size += 1;
                return Ok(());
            }
        }
        
        // 添加新条目
        bucket.push(HashEntry { key, value });
        self.size += 1;
        
        Ok(())
    }
    
    /// 查找键
    pub fn lookup(&self, key: &Value) -> Option<usize> {
        let hash = self.hash_key(key);
        let bucket_index = hash % self.bucket_count;
        
        let bucket = &self.buckets[bucket_index];
        for entry in bucket {
            if entry.key == *key {
                return Some(entry.value);
            }
        }
        
        None
    }
    
    /// 查找所有匹配的值（支持重复键）
    pub fn lookup_all(&self, key: &Value) -> Vec<usize> {
        let hash = self.hash_key(key);
        let bucket_index = hash % self.bucket_count;
        
        let bucket = &self.buckets[bucket_index];
        let mut results = Vec::new();
        
        for entry in bucket {
            if entry.key == *key {
                results.push(entry.value);
            }
        }
        
        results
    }
    
    /// 删除键
    pub fn delete(&mut self, key: &Value) -> Result<()> {
        let hash = self.hash_key(key);
        let bucket_index = hash % self.bucket_count;
        
        let bucket = &mut self.buckets[bucket_index];
        let original_len = bucket.len();
        
        bucket.retain(|entry| entry.key != *key);
        
        let removed_count = original_len - bucket.len();
        self.size -= removed_count;
        
        Ok(())
    }
    
    /// 清空索引
    pub fn clear(&mut self) {
        for bucket in &mut self.buckets {
            bucket.clear();
        }
        self.size = 0;
    }
    
    /// 获取索引大小
    pub fn size(&self) -> usize {
        self.size
    }
    
    /// 计算负载因子
    pub fn load_factor(&self) -> f64 {
        self.size as f64 / self.bucket_count as f64
    }
    
    /// 计算内存使用量
    pub fn memory_usage(&self) -> usize {
        let bucket_overhead = self.bucket_count * std::mem::size_of::<Vec<HashEntry>>();
        let entry_size = self.size * std::mem::size_of::<HashEntry>();
        bucket_overhead + entry_size
    }
    
    /// 获取统计信息
    pub fn get_statistics(&self) -> HashStatistics {
        let mut max_chain_length = 0;
        let mut total_chain_length = 0;
        let mut empty_buckets = 0;
        
        for bucket in &self.buckets {
            let chain_length = bucket.len();
            if chain_length == 0 {
                empty_buckets += 1;
            } else {
                max_chain_length = max_chain_length.max(chain_length);
                total_chain_length += chain_length;
            }
        }
        
        let avg_chain_length = if self.bucket_count > empty_buckets {
            total_chain_length as f64 / (self.bucket_count - empty_buckets) as f64
        } else {
            0.0
        };
        
        HashStatistics {
            total_entries: self.size,
            bucket_count: self.bucket_count,
            load_factor: self.load_factor(),
            max_chain_length,
            avg_chain_length,
            empty_buckets,
        }
    }
    
    /// 扩容哈希表
    fn resize(&mut self) -> Result<()> {
        let old_buckets = std::mem::take(&mut self.buckets);
        let new_bucket_count = self.bucket_count * 2;
        
        self.buckets = vec![Vec::new(); new_bucket_count];
        self.bucket_count = new_bucket_count;
        self.size = 0;
        
        // 重新插入所有条目
        for bucket in old_buckets {
            for entry in bucket {
                self.insert(entry.key, entry.value)?;
            }
        }
        
        Ok(())
    }
    
    /// 计算键的哈希值
    fn hash_key(&self, key: &Value) -> usize {
        let mut hasher = DefaultHasher::new();
        
        match key {
            Value::Integer(i) => i.hash(&mut hasher),
            Value::Real(f) => f.to_bits().hash(&mut hasher),
            Value::Text(s) => s.hash(&mut hasher),
            Value::Boolean(b) => b.hash(&mut hasher),
            Value::Null => 0_u8.hash(&mut hasher),
            Value::Timestamp(ts) => ts.hash(&mut hasher),
            Value::Decimal(d) => d.hash(&mut hasher),
        }
        
        hasher.finish() as usize
    }
    
    /// 验证哈希索引的完整性
    pub fn validate(&self) -> Result<()> {
        let mut actual_size = 0;
        
        for bucket in &self.buckets {
            actual_size += bucket.len();
        }
        
        if actual_size != self.size {
            return Err(Error::index(format!(
                "哈希索引大小不一致: 期望 {}, 实际 {}",
                self.size, actual_size
            )));
        }
        
        Ok(())
    }
    
    /// 获取桶的分布情况（用于调试）
    pub fn get_bucket_distribution(&self) -> Vec<usize> {
        self.buckets.iter().map(|bucket| bucket.len()).collect()
    }
    
    /// 设置负载因子阈值
    pub fn set_load_factor_threshold(&mut self, threshold: f64) {
        self.load_factor_threshold = threshold.clamp(0.1, 1.0);
    }
    
    /// 预分配空间
    pub fn reserve(&mut self, additional: usize) -> Result<()> {
        let target_size = self.size + additional;
        let target_load_factor = target_size as f64 / self.bucket_count as f64;
        
        if target_load_factor > self.load_factor_threshold {
            let required_buckets = (target_size as f64 / self.load_factor_threshold).ceil() as usize;
            let new_bucket_count = required_buckets.next_power_of_two();
            
            if new_bucket_count > self.bucket_count {
                let old_buckets = std::mem::take(&mut self.buckets);
                self.buckets = vec![Vec::new(); new_bucket_count];
                self.bucket_count = new_bucket_count;
                self.size = 0;
                
                // 重新插入所有条目
                for bucket in old_buckets {
                    for entry in bucket {
                        self.insert(entry.key, entry.value)?;
                    }
                }
            }
        }
        
        Ok(())
    }
    
    /// 压缩哈希表（减少内存使用）
    pub fn shrink_to_fit(&mut self) -> Result<()> {
        let optimal_bucket_count = (self.size as f64 / self.load_factor_threshold).ceil() as usize;
        let optimal_bucket_count = optimal_bucket_count.max(16).next_power_of_two();
        
        if optimal_bucket_count < self.bucket_count {
            let old_buckets = std::mem::take(&mut self.buckets);
            self.buckets = vec![Vec::new(); optimal_bucket_count];
            self.bucket_count = optimal_bucket_count;
            self.size = 0;
            
            // 重新插入所有条目
            for bucket in old_buckets {
                for entry in bucket {
                    self.insert(entry.key, entry.value)?;
                }
            }
        }
        
        Ok(())
    }
}

impl Default for HashIndex {
    fn default() -> Self {
        Self::new(16)
    }
}
